Okay, let's start.

Yesterday.

Keiner draußen gelassen.

Yesterday we talked about a different class of search algorithms, which we call local

search.

The idea there was that for certain problems, the search spaces are so high dimensional,

that you can't actually afford to be systematic because you reach the giga node barrier, which

is kind of up to a billion nodes we can do somehow.

Where you reach that barrier after a search depth of three.

The idea is to let go of systematisimity, we're letting go of completeness that way as well

and optimality anyway and do something less memory demanding.

The idea there is that you keep only one or a few search nodes in memory, everything else

you forget.

So no fringe anymore or tiny little teensy weensy little fringe and the class of algorithms

we get there is something we call local search algorithms.

Those get by without a lot of memory, but also don't give you things like repeated state

checking because you have to remember something for that or recording the solution path that

takes memory as well.

We just basically do these things for what we call configuration problems.

You just have a configuration like eight queens, you have a solution, it's easy to check that

this is indeed a solution, but how you came there, we're not interested in and we don't

know.

Same thing for factory layout or so, if you can tell this is a good solution, then you

don't want to know what was my thought process for putting this machine here, I don't care

as long as it makes me money.

So integrated circuit design, all of those kind of things we do traditionally by local

search and in a way local search or search at all isn't really considered AI anymore

because we understand it well.

So we'll play with eight queens, no we did play with eight queens.

This is not the mode I wanted.

I thought it was this.

Let's see, yeah that works.

Climbing salesman problem is a known hard problem which is in this class and we looked

at these things.

We looked at an algorithm, extremely simple algorithm.

We call it hill climbing because that's exactly what you do.

In every state you compute the successor states which there might be a few if you have a

branching factor of a thousand, that is a thousand successor states and then you pick

the best one and greedily kind of follow the steepest hill you can find with a hope to

get to the overall summit in say Everest.

We looked at a concrete example of eight queens and that is something where you kind of see

two things here.

One is that it's still as important how we represent the problem and this is a particularly

nice problem representation where we basically every board we represent as an eight topple

of digits between one and eight.

We know that if there is two queens in one column then that's not going to be a solution

anyway so we can restrict and go for a very simple representation.

The idea here is that we compute for all the possible moves and we restrict queens to

move in their column and we compute the number of successor states.

We have 64 minus eight successor states here so we have a 56 dimensional problem, branching